# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        def mergeTwoLists( l1: ListNode, l2: ListNode):
            if not l1:
                return l2
            if not l2:
                return l1
            if l1.val>l2.val:
                temp=l2
                l2=l1
                l1=temp
            temp=l1
            while l2:
                while temp.next and l2.val>temp.next.val:
                    temp=temp.next
                record1=temp.next
                record2=l2.next
                temp.next=l2
                l2.next=record1
                l2=record2
            return l1
        head=ListNode()
        if len(lists)==0:
            return None
        while len(lists)!=1:
            out=[]
            for i in range(0,len(lists),2):
                if i+1<len(lists):
                    out.append(mergeTwoLists(lists[i],lists[i+1]))
                else:
                    out.append(lists[i])
            lists=out
        return lists[0]

'''
分治算法
'''
'''
执行用时：
96 ms
, 在所有 Python3 提交中击败了
86.41%
的用户
内存消耗：
17.8 MB
, 在所有 Python3 提交中击败了
59.35%
的用户
'''